public class No_02_SwapPair {

    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 3, 1};
        System.out.println(swapPairs(arr, 0, arr.length - 1));
    }

    public static int swapPairs(int[] arr, int left, int right) {
        if (arr == null || right == left) {
            return 0;
        }

        int middle = (left + right) / 2;
        return swapPairs(arr, left, middle) + swapPairs(arr, middle + 1, right) + merge(arr, left, middle, right);
    }

    public static int merge(int[] arr, int start, int middle, int end) {

        int tempSum = 0;
        // 最小和
        int smallSum = 0;

        for (int left = start, right = middle + 1; left <= middle; left++) {
            while (right <= end && arr[left] > 2 * arr[right]) {
                tempSum += 1;
                right++;
            }
            smallSum += tempSum;
        }

        // 保证数组有序
        int fillIndex = 0;
        int leftIndex = start;
        int rightIndex = middle + 1;
        int[] helper = new int[end - start + 1];
        while (leftIndex <= middle && rightIndex <= end) {
            helper[fillIndex++] = arr[leftIndex] < arr[rightIndex] ? arr[leftIndex++] : arr[rightIndex++];
        }
        while (leftIndex <= middle) {
            helper[fillIndex++] = arr[leftIndex++];
        }
        while (rightIndex <= end) {
            helper[fillIndex++] = arr[rightIndex++];
        }
        System.arraycopy(helper, 0, arr, start, end + 1 - start);

        return smallSum;
    }

}
